package ink.lovejinhu.swardToOffer;

import ink.lovejinhu.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: jin
 * @Date: 2021/8/27 15:25
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/
public class Offer_068_II {
    /**
     * 二叉树最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayList<TreeNode> treeNodeP = new ArrayList<>();
        ArrayList<TreeNode> treeNodeQ = new ArrayList<>();
        this.dfs(root, p, treeNodeP);
        this.dfs(root, q, treeNodeQ);

        for (int i = treeNodeP.size() - 1; i >= 0; i--) {
            for (int j = treeNodeQ.size() - 1; j >= 0; j--) {
                if (treeNodeP.get(i).val == treeNodeQ.get(j).val) {
                    return treeNodeP.get(i);
                }
            }
        }
        return null;
    }

    /**
     * 找出p的所有父节点
     *
     * @param root
     * @param p
     */
    public void dfs(TreeNode root, TreeNode p, List<TreeNode> parent) {
        if (root == null) {
            parent.clear();
            return;
        }
        parent.add(root);
        if (root.val == p.val) {
            return;
        } else {
            ArrayList<TreeNode> treeNodes = new ArrayList<>();
            dfs(root.left, p, treeNodes);
            if (treeNodes.size() != 0) {
                for (int i = 0; i < treeNodes.size(); i++) {
                    parent.add(treeNodes.get(i));
                }
                return;
            }
            dfs(root.right, p, parent);
            ArrayList<TreeNode> treeNode = new ArrayList<>();
            if (treeNode.size() != 0) {
                for (int i = 0; i < treeNode.size(); i++) {
                    parent.add(treeNode.get(i));
                }
                return;
            }
        }
    }

}
